package com.sl.sort

import java.util.*
import kotlin.math.max

/**
 * author： suliang
 * 2022/11/4 15:08
 * describe : 排序工具
 */
class SortUtils {

    companion object {

        @JvmStatic
        fun forGrammar() {
            val array = arrayOf(
                1,
                3,
                5,
                6,
                7,
                3,
                2,
                56,
                78,
                9,
                233,
                357,
                7,
                457,
                5565,
                44,
                32,
                122,
                33,
                322,
                45,
                445
            )

            println("---------------- 基本for循环")
            for (item in array) {
                print("$item,")
            }
            println("\n---------------- 区间表达式,正序")
            for (i in 0..5) {
                print("$i,")
            }
            println("\n---------------- 区间表达式，倒序")
            for (i in 6 downTo 0 step 1) {
                print("$i,")
            }
            println("\n---------------- 通过索引遍历")
            for (i in array.indices) {
                print("$i -> ${array[i]},")
            }
            println("\n---------------- 库函数 withIndex")
            for ((index, value) in array.withIndex()) {
                print("$index -> $value,")
            }

            println("\n---------------- downTo")
            for (i in array.size-1 downTo 0){
                println(i)
            }

        }

        /**
         * 冒泡排序
         * @param array
         */
        @JvmStatic
        fun bubbleSort(array: Array<Int>) {
            for (i in 1 until array.size) {
                var flag = true    //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
                for (j in 0 until array.size - i) {
                    if (array[j] > array[j + 1]) {
                        val temp = array[j]
                        array[j] = array[j + 1]
                        array[j + 1] = temp
                        flag = false
                    }
                }
                if (flag) {
                    break
                }
            }
        }

        /**
         * 选择排序
         * @param array
         */
        @JvmStatic
        fun selectionSort(array: Array<Int>) {
            //总共要经过N-1轮比较
            for (i in 0 until array.size - 1) {
                var min = i         //记录比较值为最小值
                //每轮需要比较的次数 N-i
                for (j in i + 1 until array.size) {
                    if (array[j] < array[min]) {
                        //记录目前找到的最小值元素的下标
                        min = j
                    }
                }
                //将最小值和i位置所在的值进行交换
                if (min != i) {
                    val temp = array[i]
                    array[i] = array[min]
                    array[min] = temp
                }
            }
        }

        /**
         * 插入排序
         * @param array
         */
        @JvmStatic
        fun insertSort(array: Array<Int>) {
            //从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
            for (i in 1 until array.size) {
                //记录要插入的数据
                val temp = array[i]
                //从已经排序的序列的最右边的开始比较，找到比其小的数
                var j = i
                while (j > 0 && temp < array[j - 1]) {
                    array[j] = array[j - 1]
                    j--
                }
                //存在比其小的数，插入
                if (j != i) {
                    array[j] = temp
                }
            }
        }

        /**
         * 希尔排序
         */
        @JvmStatic
        fun shellSort(arr: Array<Int>) {
            var temp: Int
            var step = arr.size / 2
            while (step >= 1) {
                for (i in step until arr.size) {
                    temp = arr[i]
                    var j = i - step
                    while (j >= 0 && arr[j] > temp) {
                        arr[j + step] = arr[j]
                        j -= step
                    }
                    arr[j + step] = temp
                }
                step /= 2
            }
        }

        /**
         * 归并排序
         * @param arr
         */
        @JvmStatic
        fun mergeSort(arr: Array<Int>): Array<Int> {
            if (arr.size < 2)
                return arr
            val middle: Int = arr.size / 2
            val left = Arrays.copyOfRange(arr, 0, middle)
            val right = Arrays.copyOfRange(arr, middle, arr.size)
            return merge(mergeSort(left), mergeSort(right))
        }

        private fun merge(_left: Array<Int>, _right: Array<Int>): Array<Int> {
            var left = _left
            var right = _right
            val result = Array<Int>(left.size + right.size) { 0 }
            for (x in result) {
                print("$x,")
            }
            var i = 0
            while (left.isNotEmpty() && right.isNotEmpty()) {
                if (left[0] <= right[0]) {
                    result[i++] = left[0]
                    left = left.copyOfRange(1, left.size)
                } else {
                    result[i++] = right[0]
                    right = right.copyOfRange(1, right.size)
                }
            }
            while (left.isNotEmpty()) {
                result[i++] = left[0]
                left = left.copyOfRange(1, left.size)
            }
            while (right.isNotEmpty()) {
                result[i++] = right[0]
                right = right.copyOfRange(1, right.size)
            }
            return result
        }

        /**
         * 快速排序
         * @param left： first 0
         * @param right ： first arr.length - 1
         */
        fun quickSort(array: Array<Int>, left: Int, right: Int) {
            if (left < right) {
                val partitionIndex = partition(array, left, right)
                quickSort(array, left, partitionIndex - 1)
                quickSort(array, partitionIndex + 1, right)
            }
        }

        private fun partition(array: Array<Int>, left: Int, right: Int): Int {
            val pivot = left            //设定基准值 pivot ，基准为第一位
            var index = pivot + 1        //基准下一位 开始循环
            for (i in index..right) {
                if (array[i] < array[pivot]) { //基准值右侧的值小于基准值
                    swap(array, i, index)
                    index++
                }
            }
            swap(array, pivot, index - 1)    // index左边的值都是小于基础的值，这里进行交换
            return index - 1
        }

        private fun swap(array: Array<Int>, i: Int, j: Int) {
            val temp = array[i]
            array[i] = array[j]
            array[j] = temp
        }


        /**
         * 堆排序
         */
        fun headSort(array: Array<Int>){
            var len = array.size
            buildMaxHead(array,len)
            for (i in len -1 downTo 1 ){
                swap(array,0,i)
                len --
                heapify(array,0,len)
            }
        }

        private fun buildMaxHead(array: Array<Int>,len : Int) {
            var i = Math.floor((array.size/2).toDouble()).toInt()
            while (i >= 0 ){
                heapify(array,i,len)
                i--
            }
        }
        private fun heapify(array: Array<Int>, i:Int, len: Int){
            val left = 2*i + 1
            val right = 2*i + 2
            var largest = i
            if (left < len && array[left] > array[largest]){
                largest = left
            }
            if (right < len && array[right] > array[largest]){
                largest = right
            }
            if (largest != i){
                swap(array,i,largest)
                heapify(array,largest,len)
            }
        }

        /**
         * 计数排序
         */
        fun countingSort(array: Array<Int>){
            val maxValue = getMaxValue(array)
            val bucket = Array<Int>(maxValue + 1){ 0 }       //定义桶数组
            array.forEach {
                bucket[it]++
            }
            var sortIndex = 0
            bucket.indices.forEach {  i ->      //下标循环
                while (bucket[i] > 0){
                    array[sortIndex++] = i
                    bucket[i]--
                }
            }
        }
        /** 获取最大的值  */
        private fun getMaxValue(array: Array<Int>) : Int{
            var maxValue = array[0]
            array.forEach { value ->
                if (maxValue < value){
                    maxValue = value
                }
            }
            return maxValue
        }

        /**
         * 桶排序
         */
        fun bucketSort(array: Array<Int>){
            if (array.isEmpty()) return
            val bucketSize  = 5         //定义桶数量
            //获取最大最小的值
            var minValue = array[0]
            var maxValue = array[0]
            array.forEach { value ->
                if (value < minValue){
                    minValue = value
                }else if (value > maxValue){
                    maxValue = value
                }
            }

            val bucketCount = Math.floor(((maxValue - minValue) / bucketSize).toDouble()).toInt() + 1
            val buckets = Array(bucketCount) { Array(0){0} }
            //利用映射讲数据分配到每个桶里
            array.forEachIndexed { i, value ->
                val index = Math.floor((value - minValue) / bucketSize.toDouble()).toInt()
                buckets[index] = arrAppend(buckets[index],value)
            }
            var arrIndex = 0
            buckets.forEach { value: Array<Int> ->
                if (value.isEmpty()){
                    return
                }
                //对每个桶进行排序，这里适用插入排序
                insertSort(value)
                value.forEach {
                    array[arrIndex++] = it
                }
            }
        }
        /** 自动扩容并保存数据 */
        private fun arrAppend(ints: Array<Int>, value: Int): Array<Int> {
            val arr  = Arrays.copyOf(ints,ints.size + 1)
            arr[arr.size - 1] = value
            return arr
        }

        /**
         * 基数排序
         */
        fun radixSort(array: Array<Int>){
            val maxDigit = getMaxDigit(array)
            var mod = 10
            var dev = 1
            var i = 0
            while (i < maxDigit){
                //考虑负数的情况，扩展一倍队列，其中[0-9]对应负数，[10-19]对应正数
                val counter = Array(mod * 2){ Array(0){0} }

                array.forEachIndexed{ index,value ->
                    val bucket = ((value % mod) / dev ) + mod
                    counter[bucket] = arrAppend(counter[bucket],value)
                }
                var pos = 0
                counter.forEach { value ->
                    value.forEach {  v ->
                        array[pos++] = v
                    }
                }
                i++
                dev *= 10
                mod *= 10
            }
        }
        /**
         * 获取最高位数
         */
        private fun getMaxDigit(array: Array<Int>) : Int {
            val maxValue = getMaxValue(array)
            return getNumLength(maxValue)
        }
        private fun getNumLength(value: Int) : Int {
            if (value == 0) return  1
            var length = 0
            var temp : Int = value
            while (temp != 0 ){
                length++
                temp /= 10
            }
            return length
        }

    }
}